Matching techniques are often used to optimize integrated circuit designs or software programs to reduce power consumption, area and cost, or to increase performance such as operating frequency and/or data throughput. Such matching techniques have been shown to be useful in several fields including high-level synthesis of digital logic and compilers for software programs. Integrated circuits and other electronic systems include binary logic or other hardware structures to perform the functions that each circuit was designed to achieve. Likewise, compilers for software programs include data structures to perform the functions that the program was designed to achieve.
Generally, matching techniques are applied to either the structures or the functions of integrated circuit designs and software programs. Structural matching techniques seek to identify separate structures within the design of an integrated circuit or software program and to combine those structures, to the extent possible, into a single structure or subset of structures that perform the same overall function as each of the separate structures individually or the same function as all structures together. Functional matching techniques, on the other hand, seek to identify separate functions within the design of an integrated circuit or a software program and combine those functions into a single function or subset of functions that perform the same overall function as each of the separate functions individually or the same function as all structures together.
This combining of structures and/or functions may be referred to as resource sharing. FIG. 1 illustrates resource sharing among modules with identical circuitry and/or functionality according to the prior art. FIG. 1 includes two identical circuits and/or functional modules, clone A 101 and clone B 102, having the same I/O signals, IN0 and OUT0, respectively. Since clone A 101 and clone B 102 contain identical circuitry and/or functionality and the same I/O, clone A 101 and clone B 102 are identified as candidates for sharing. Thus, clone A 101 and clone B 102 each includes identical circuitry and/or functionality that may be shared by both clone A 101 and clone B 102. This sharing of resources among identical circuits and/or functions is achieved by replacing clone A 101 and clone B 102 with a single shared resource 103 and appropriately routing the common I/O. The structure and/or functionality of both clone A 101 and clone B 102 is maintained, but the resources required by the circuit are reduced through resource sharing.
Integrated circuit designs and/or software programs include various structures to perform various functions. These structures may include different structures that perform different functions, similar structures that perform identical functions, identical structures that perform identical functions, and different structures that perform identical functions. Likewise, integrated circuit designs and/or software programs may include identical functions implemented using identical structures, identical functions implemented using similar or different structures, different functions implemented using similar structures, and different functions implemented using different structures.
The goal of matching techniques is to identify structures and/or functionality in an integrated circuit design or software program that can be matched to enable resource sharing to the extent possible. However, previously known techniques are limited to either exact matching or matching in terms of design descriptions, leaving some matches undetected. Conventional matching techniques have been limited to either exact functional matching, or exact and approximate structural matching. For example, the 2008 publication by J. Cong and W. Jiang entitled “Pattern-based Behavior Synthesis for FPGA Resource Reduction,” Proc. ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA 2008) performs only structural matching techniques. The Cong publication finds bridging points of certain graphs to perform structural matching of integrated circuit hardware.
Several precursors of the Cong publication are also limited to structural matching including the following: L. Pozzi, K. Atasu, P. Ienne, “Exact and Approximate Algorithms for the Extension of Embedded Processor Instruction Sets,” IEEE Trans. on CAD 25(7), July 2006; X. Chen, D. L. Maskell, Y. Sun, “Fast Identification of Custom Instructions for Extensible Processors,” IEEE Trans. on CAD 26(2), February 2007; M. R. Corazao, M. Khalaf, L. Guerra, M. Potkonjak and J. M. Rabaey, “Performance Optimization Using Template Matching for Datapath-Intensive High-Level Synthesis,” IEEE Trans. on CAD 15(8), August 1996, and A. Raghunathan and N. K. Jha, “SCALP: An Iterative-Improvement Based Low-Power Data Path Synthesis System,” IEEE Trans. on CAD 16(11), November 1997.
In the category of functional matching, the recent publication by M. Ciesielski, S. Askar, D. Gomez-Prado, J. Guillot, E. Boutillon, entitled “Data-Flow Transformations using Taylor Expansion Diagrams,” Proc. ACM/IEEE Design Automation Conference (DAC) 2007, performs exact functional matching only. Likewise, the publication by P. Tummeltshammer, J. C. Hoe, M. Pueschel, entitled “Time-Multiplexed Multiple-Constant Multiplication,” IEEE TCAD 26(9), September 2007 is based on exact functional matching. The Tummeltshammer publication is applicable only to subsets of designs that perform multiplication by pre-determined constants, and only in the context of multiplication circuits. An earlier publication by P. Flores, J. Monteiro, E. Costa, entitled “An Exact Algorithm for the Maximal Sharing of Partial Terms in Multiple Constant Multiplications”, Proc. ACM/IEEE Int'l Conf. on CAD (ICCAD 2005) on sharing resources among multiplication circuits exhibits the same limitations as Ciesielski and Tummeltshammer. The publication by A. Verma and P. Ienne entitled, “Improved use of the carry-save representation for the synthesis of complex arithmetic circuits,” in Proceedings of ICCAD 2007 discloses a representation of arithmetic circuits that facilitates algorithms for exact functional matching. Similar techniques based on circuit transformations have been pursued in more recent art, but generally share the same limitations.
In the case of functional matching, it is well-known that designs that perform the same function, regardless of their internal structure, can be functionally matched to enable resource sharing. In the case of structural mapping, identical or similar structures may be matched whether or not they perform identical functions.
Another line of prior art is motivated by techniques that have been proposed for specialized physical layout of datapath circuits, exemplified by the U.S. Pat. No. 5,737,237 entitled “Method and apparatus for data path circuit layout design and memory medium for causing computer to execute datapath design,” and U.S. Pat. No. 6,560,761 entitled “Method of datapath cell placement for bitwise and non-bitwise integrated circuits.” These techniques teach receiving as input a datapath description for a datapath block and either prepare or receive function macros in each of which there is a defined expansion to a circuit comprising a plurality of schematic leaf cells. These techniques are commonly described for gate-level circuits.
In practice, datapath circuits can and often are extracted by design engineers. Since datapaths circuits (particularly adders and multipliers) may admit compact and regular layout, attempts have been made at “regularity extraction,” often focusing on array-like structures and repeated components. S. Hassoun and C. McCreary in their ICCAD 1999 paper entitled, “Regularity extraction via clan-based structural circuit decomposition,” points out that identifying repeating structural regularities in circuits allows the minimization of synthesis, optimization and layout efforts. They term these repeated structures “templates” and cover the circuit with an appropriate set of templates. U.S. Pat. No. 6,148,433 entitled, “Systematic approach for regularity extraction,” also teaches generating a set of templates for a circuit through computer automated operations on a description of the circuit. The method includes covering the circuit with instances of a subset of the templates. Such templates may include adders, multipliers, and larger configurations.
S. R. Arikati and R. Varadarajan in their ICCAD 1997 paper entitled, “A signature based approach to regularity extraction,” computes numerical signatures of circuit components and identifies similar components when different signatures match, U.S. Pat. No. 6,557,159 entitled, “Method for preserving regularity during logic synthesis,” also determines a group of elements in a circuit netlist having similar regularity signatures. In this case, regularity is determined based on a physical layout of the circuit. Further, this patent teaches determining a regularity signature for each element within the group and determining whether the regularity signatures for each element are identical.
U.S. Pat. No. 7,337,418 entitled, “Structural regularity extraction and floorplanning in datapath circuits using vectors,” distinguishes a functional regularity extraction component, a structural regularity extraction component, and a floorplanning component. Some embodiments of the functional regularity extraction component automatically generate a set of templates to cover a circuit. The templates generated by the functional regularity extraction component are used by a structural regularity extraction component. While particularly noting regularity in datapath circuits and focusing on templates, this patent also teaches identifying control logic for the logic design and excluding the control logic from the set of vectors. A vector is a group of template instances that are identical in function and in structure. The techniques described in this patent are structural as they consider two subgraphs functionally equivalent, if and only if the following: (a) if they are isomorphic; (b) the logic functions of corresponding nodes are the same; and (c) the indices of corresponding edges are also the same. Under this criterion, the functional equivalence of (a+b)*c and (a*c+b*c), even though obvious to a person skilled in the art, cannot be established. While focusing on template covering and physical layout, the patent does not explain how one may identify control or datapath.